/**
 * 猫咪移动地图生成器
 * 生成适合猫咪持续移动的地图，避免死路和平行通道
 */

// 生成猫咪移动地图
export const generateMaze = (rows, cols) => {
  // 确保参数有效
  if (!rows || !cols || rows < 5 || cols < 5) {
    rows = 15
    cols = 15
  }
  
  const adjustedRows = rows % 2 === 0 ? rows + 1 : rows
  const adjustedCols = cols % 2 === 0 ? cols + 1 : cols
  
  return generateCatMovementMap(adjustedRows, adjustedCols)
}

// 猫咪移动地图生成算法
const generateCatMovementMap = (rows, cols) => {
  // 初始化地图，所有格子都是墙
  const map = Array(rows).fill().map(() => Array(cols).fill(1))
  
  // 第一步：生成主要道路网络
  generateMainRoads(map, rows, cols)
  
  // 第二步：添加路口连接
  addIntersections(map, rows, cols)
  
  // 第三步：确保边界可通过
  makeBoundaryPassable(map, rows, cols)
  
  // 第四步：优化连通性，移除死路
  optimizeConnectivity(map, rows, cols)
  
  return map
}

// 生成主要道路网络
const generateMainRoads = (map, rows, cols) => {
  // 生成水平主要道路
  const horizontalRoads = Math.floor(rows / 4)
  for (let i = 1; i <= horizontalRoads; i++) {
    const row = Math.floor((rows * i) / (horizontalRoads + 1))
    if (row > 0 && row < rows - 1) {
      for (let col = 0; col < cols; col++) {
        map[row][col] = 0
      }
    }
  }
  
  // 生成垂直主要道路
  const verticalRoads = Math.floor(cols / 4)
  for (let i = 1; i <= verticalRoads; i++) {
    const col = Math.floor((cols * i) / (verticalRoads + 1))
    if (col > 0 && col < cols - 1) {
      for (let row = 0; row < rows; row++) {
        map[row][col] = 0
      }
    }
  }
}

// 添加路口连接
const addIntersections = (map, rows, cols) => {
  // 在主要道路之间添加一些连接道路
  const connectionCount = Math.floor((rows + cols) / 3)
  
  for (let i = 0; i < connectionCount; i++) {
    // 随机选择连接类型：水平或垂直
    const isHorizontal = Math.random() > 0.5
    
    if (isHorizontal) {
      // 添加水平连接道路
      const row = Math.floor(Math.random() * (rows - 2)) + 1
      const startCol = Math.floor(Math.random() * (cols - 4)) + 1
      const endCol = startCol + Math.floor(Math.random() * 3) + 2
      
      // 检查是否与现有道路平行
      if (!hasParallelRoad(map, row, startCol, endCol, true, rows, cols)) {
        for (let col = startCol; col <= Math.min(endCol, cols - 2); col++) {
          map[row][col] = 0
        }
      }
    } else {
      // 添加垂直连接道路
      const col = Math.floor(Math.random() * (cols - 2)) + 1
      const startRow = Math.floor(Math.random() * (rows - 4)) + 1
      const endRow = startRow + Math.floor(Math.random() * 3) + 2
      
      // 检查是否与现有道路平行
      if (!hasParallelRoad(map, col, startRow, endRow, false, rows, cols)) {
        for (let row = startRow; row <= Math.min(endRow, rows - 2); row++) {
          map[row][col] = 0
        }
      }
    }
  }
}

// 检查是否存在平行道路
const hasParallelRoad = (map, pos, start, end, isHorizontal, rows, cols) => {
  if (isHorizontal) {
    // 检查水平道路的上下是否有平行道路
    const row = pos
    for (let col = start; col <= end; col++) {
      // 检查上方
      if (row > 1 && map[row - 1][col] === 0) {
        return true
      }
      // 检查下方
      if (row < rows - 2 && map[row + 1][col] === 0) {
        return true
      }
    }
  } else {
    // 检查垂直道路的左右是否有平行道路
    const col = pos
    for (let row = start; row <= end; row++) {
      // 检查左侧
      if (col > 1 && map[row][col - 1] === 0) {
        return true
      }
      // 检查右侧
      if (col < cols - 2 && map[row][col + 1] === 0) {
        return true
      }
    }
  }
  return false
}

// 确保边界可通过
const makeBoundaryPassable = (map, rows, cols) => {
  // 设置上边界为路径
  for (let col = 0; col < cols; col++) {
    map[0][col] = 0
  }
  
  // 设置下边界为路径
  for (let col = 0; col < cols; col++) {
    map[rows - 1][col] = 0
  }
  
  // 设置左边界为路径
  for (let row = 0; row < rows; row++) {
    map[row][0] = 0
  }
  
  // 设置右边界为路径
  for (let row = 0; row < rows; row++) {
    map[row][cols - 1] = 0
  }
}

// 优化连通性，移除死路
const optimizeConnectivity = (map, rows, cols) => {
  // 标记所有可达的路径
  const visited = Array(rows).fill().map(() => Array(cols).fill(false))
  
  const markConnected = (row, col) => {
    if (row < 0 || row >= rows || col < 0 || col >= cols || 
        map[row][col] === 1 || visited[row][col]) {
      return
    }
    
    visited[row][col] = true
    
    const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    for (const [dr, dc] of directions) {
      markConnected(row + dr, col + dc)
    }
  }
  
  // 从边界开始标记所有可达的路径
  for (let col = 0; col < cols; col++) {
    markConnected(0, col)
    markConnected(rows - 1, col)
  }
  for (let row = 0; row < rows; row++) {
    markConnected(row, 0)
    markConnected(row, cols - 1)
  }
  
  // 将未访问的路径区域转换为墙
  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (map[row][col] === 0 && !visited[row][col]) {
        map[row][col] = 1
      }
    }
  }
  
  // 移除死路（只有一个出口的路径）
  removeDeadEnds(map, rows, cols)
}

// 移除死路
const removeDeadEnds = (map, rows, cols) => {
  let hasDeadEnds = true
  
  while (hasDeadEnds) {
    hasDeadEnds = false
    
    for (let row = 1; row < rows - 1; row++) {
      for (let col = 1; col < cols - 1; col++) {
        if (map[row][col] === 0) {
          const neighbors = countPathNeighbors(map, row, col, rows, cols)
          
          // 如果只有一个邻居，说明是死路
          if (neighbors === 1) {
            map[row][col] = 1
            hasDeadEnds = true
          }
        }
      }
    }
  }
}

// 计算路径邻居数量
const countPathNeighbors = (map, row, col, rows, cols) => {
  const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
  let count = 0
  
  for (const [dr, dc] of directions) {
    const newRow = row + dr
    const newCol = col + dc
    
    if (newRow >= 0 && newRow < rows && 
        newCol >= 0 && newCol < cols && 
        map[newRow][newCol] === 0) {
      count++
    }
  }
  
  return count
}

// 生成简单测试地图（备用）
export const generateSimpleMaze = (rows, cols) => {
  const map = Array(rows).fill().map(() => Array(cols).fill(0))
  
  // 添加一些随机墙壁，但确保有足够的移动空间
  const wallCount = Math.floor((rows * cols) * 0.15)
  
  for (let i = 0; i < wallCount; i++) {
    const row = Math.floor(Math.random() * rows)
    const col = Math.floor(Math.random() * cols)
    
    // 确保不在边界位置
    if (row > 0 && row < rows - 1 && col > 0 && col < cols - 1) {
      map[row][col] = 1
    }
  }
  
  // 确保边界是路径
  makeBoundaryPassable(map, rows, cols)
  
  // 移除死路
  removeDeadEnds(map, rows, cols)
  
  return map
}